//
// Created by 麻再挺 on 2021/12/13.
//

#include "bi_tree.h"
#include "../stack_queue/queue.h"

/**
 * 按先序次序输入二叉树中结点的值, 空格字符表示空树
 * @param t 二叉树
 * @return
 */
Status CreateBiTree(BiTree *t) {
    // 从控制台获取数据
    char ch;
    scanf("%c", &ch);
    if (ch != ' ' && ch != '\n') {
//        if (!(t = malloc(sizeof(BiTree)))) exit(OVERFLOW);
        // 赋值, 生成根节点
        t->data = ch;
        if (!(t->lChild = malloc(sizeof(BiTree)))) exit(OVERFLOW);
        // 索引自加
        // 构造左子树
        CreateBiTree(t->lChild);
        if (!(t->rChild = malloc(sizeof(BiTree)))) exit(OVERFLOW);
        // 构造右子树
        CreateBiTree(t->rChild);
        // 如果左子树或右子树节点值为'\0', 则代表是空
        if (t->lChild->data == '\0') {
            free(t->lChild);
            t->lChild = NULL;
        }
        if (t->rChild->data == '\0') {
            free(t->rChild);
            t->rChild = NULL;
        }
    }
    return OK;
}

/**
 * 先序遍历
 * @param t
 * @return
 */
Status PreOrderTraverse(BiTree *t) {
    if (t && t->data != '\0') {
        printf("%c", t->data);
        PreOrderTraverse(t->lChild);
        PreOrderTraverse(t->rChild);
    }
    return OK;
}

/**
 * 中序遍历
 * @param t
 * @return
 */
Status InOrderTraverse(BiTree *t) {
    if (t && t->data != '\0') {
        InOrderTraverse(t->lChild);
        printf("%c", t->data);
        InOrderTraverse(t->rChild);
    }
    return OK;
}

/**
 * 后续遍历
 * @return
 */
Status PostOrderTraverse(BiTree *t) {
    if (t && t->data != '\0') {
        PostOrderTraverse(t->lChild);
        PostOrderTraverse(t->rChild);
        printf("%c", t->data);
    }
    return OK;
}

/**
 * 层序遍历
 * @param t
 * @return
 */
Status LevelOrderTraverse(BiTree *t) {
    // 初始化队列
    LinkQueue queue;
    Link_Queue_Init(&queue);
    // 将地址转换为整形值
    QElemType rootAddr = (QElemType)t;
    Link_Queue_Enter(&queue, rootAddr);
    BiTree *last = t;
    BiTree *nLast = t;
    // 循环打印
    while (!Link_Queue_Empty(&queue)) {
        // 出队
        QElemType root;
        Link_Queue_Deter(&queue, &root);
        BiTree tmp = (*(BiTree *) root);
        printf("%c\t", tmp.data);
        // 左子树
        if (tmp.lChild) {
            Link_Queue_Enter(&queue, tmp.lChild);
            nLast = tmp.lChild;
        }
        // 右子树
        if (tmp.rChild) {
            Link_Queue_Enter(&queue, tmp.rChild);
            nLast = tmp.rChild;
        }
        // 如果是最右侧节点, 则换行
        if (last == root) {
            printf("\n");
            last = nLast;
        }
    }
    return OK;
}
